package searchAlgs;

import Graph.Graph;
import Graph.Vertex;
import java.util.*;

 
/**
 *
 * @author camacho
 */
public class Dijkstra{
    private Graph graph = new Graph();
    //<Vertex id, Cost to Vertex)
    private Map<Integer,Integer> d = new HashMap();
    //<Vertex id, precursor id>
    private Map<Integer,Integer> p = new HashMap();
    //Group of vertex<Vertex id, Vertex>
    private Map<Integer, Vertex> q = new HashMap();
    
    public Dijkstra (Graph g, Vertex u){
        this.graph = g;
        //Set for cost infinity and precursor key null
        for(Map.Entry<Integer,Vertex> entry: graph.getVertexes().entrySet()){
            Integer integer = entry.getKey();
            Vertex vertex = entry.getValue();
            d.put(vertex.getId(), (int)Double.POSITIVE_INFINITY);
            p.put(vertex.getId(), null);
            q.put(vertex.getId(), vertex);
        }
        //Inicial Vertex cost
        d.put(u.getId(), 0);
        boolean inicio = true;
        while (!q.isEmpty()){
            int mincostvalue = (int)Double.POSITIVE_INFINITY;
            int mincostid = 0;
            //Lower Cost of Q
            for (Map.Entry<Integer, Integer> entry : d.entrySet()) {
                Integer key = entry.getKey();
                Integer id = entry.getValue();
                if((q.get(key)!=null)&&(id < mincostvalue)){
                   mincostvalue = id;
                   mincostid = key;
                } 
            }
            if(!inicio){
                u = graph.getVertexes().get(mincostid); 
                q.remove(mincostid);
            }else{
                q.remove(u. getId());
            }   
            for(Vertex v : u.adj()){
                relax(u, v);
            }
            inicio = false;
        }
        //Print of Vertex, Precursor Key and Cost
        for(Map.Entry<Integer,Vertex> entry: graph.getVertexes().entrySet()){
            Vertex vertex = entry.getValue();
            System.out.print("Vertex = " + vertex.getId());
            System.out.print(" (Precursor = " + p.get(vertex.getId())+", ");
            System.out.println("Cost = " + d.get(vertex.getId())+")");
        }
   }
    
    private void relax(Vertex u, Vertex v) {
        int w = (int)Double.POSITIVE_INFINITY;
        //Busca o custo entre os vertices u e v
        for (int i = 0; i < graph.getVertexes().get(u.getId()).getEdges().size(); i++) {
            if(graph.getVertexes().get(u.getId()).getEdges().get(i).getVi() == u && graph.getVertexes().get(u.getId()).getEdges().get(i).getVj() == v){
                w = graph.getVertexes().get(u.getId()).getEdges().get(i).getCost();
            }
        }
        //Se o custo ja setado para esse vertice v for maior que o novo custo encontrado seta novo custo
        if ((d.get(v.getId())) > (d.get(u.getId())+ w)){
            d.put(v.getId(), d.get(u.getId())+ w);
            p.put(v.getId(), u.getId());
        }
    }
    
    
    
    public Graph getGraph() {
        return graph;
    }

    public void setGraph(Graph graph) {
        this.graph = graph;
    }


    public Map<Integer,Integer> getD() {
        return d;
    }

    public void setD(Map<Integer,Integer> d) {
        this.d = d;
    }

    public Map<Integer,Integer> getP() {
        return p;
    }

    public void setP(Map<Integer,Integer> p) {
        this.p = p;
    }

    public Map<Integer, Vertex> getQ() {
        return q;
    }

    public void setQ(Map<Integer, Vertex> q) {
        this.q = q;
    }
}
